class Block { //方块类
	x = 0; //横坐标
	y = 0; //纵坐标
	w = 0; //宽
	h = 0; //高
	c = 0; //代号2X2->1 2X1->2 1X2->3 1X1->4 0X0->0
	constructor(x, y, w, h) { //构造函数
		this.x = x;
		this.y = y;
		this.w = w;
		this.h = h;
		if (w == 2 && h == 2) {
			this.c = 1;
		} else if (w == 1 && h == 1) {
			this.c = 4;
		} else if (w == 2 && h == 1) {
			this.c = 2;
		} else if (w == 1 && h == 2) {
			this.c = 3;
		}
	}

	left() {
		this.y--;
	}
	right() {
		this.y++;
	}
	up() {
		this.x--;
	}
	down() {
		this.x++;
	}

	clone(block) {
		return new Block(this.x, this.y, this.w, this.h);
	}
}

class Solution { //解决方案
	blocks = []; //方块数组
	row = 0; //横将个数

	constructor(blocks) { //构造函数
		this.blocks = blocks;
	}
	solve() { //求解
		if (this.over(this.blocks)) {
			return [
				[], true
			];
		}

		let aspects = new Map();
		let queue = [];

		let arr = this.toArray(this.blocks);
		for (let i = 0; i < 5; i++) {
			for (let j = 0; j < 4; j++) {
				if (arr[i][j] == 2) {
					this.row++;
				}
			}
		}
		this.row = parseInt(this.row / 2);
		if (!this.correct(arr)) {
			throw "局面格式不规范，请按照5行4列地图摆放10个方块【1个2X2，2X1+1X2共5个，4个1X1】";
		}
		let key = this.toKey(arr);

		queue.push(this.blocks);
		aspects.set(key, "");

		let solution = [
			[], false
		];
		while (queue.length > 0) {
			let now = queue.shift();
			let nowArr = this.toArray(now);
			let nowKey = this.toKey(nowArr);

			for (let i = 0; i < now.length; i++) {
				let next = this.cloneBlocks(now);
				next[i].down();
				arr = this.toArray(next);
				if (arr != false) {
					key = this.toKey(arr);
					if (!aspects.has(key)) {
						aspects.set(key, nowKey);
						queue.push(next);

						if (key[2] == 'N') {
							while (key != "") {
								solution[0].unshift(key);
								key = aspects.get(key);
							}
							solution[1] = true;
							return solution;
						}
					}
				}

				next = this.cloneBlocks(now);
				next[i].left();
				arr = this.toArray(next);
				if (arr != false) {
					key = this.toKey(arr);
					if (!aspects.has(key)) {
						aspects.set(key, nowKey);
						queue.push(next);

						if (key[2] == 'N') {
							while (key != "") {
								solution[0].unshift(key);
								key = aspects.get(key);
							}
							solution[1] = true;
							return solution;
						}
					}
				}

				next = this.cloneBlocks(now);
				next[i].right();
				arr = this.toArray(next);
				if (arr != false) {
					key = this.toKey(arr);
					if (!aspects.has(key)) {
						aspects.set(key, nowKey);
						queue.push(next);

						if (key[2] == 'N') {
							while (key != "") {
								solution[0].unshift(key);
								key = aspects.get(key);
							}
							solution[1] = true;
							return solution;
						}
					}
				}

				next = this.cloneBlocks(now);
				next[i].up();
				arr = this.toArray(next);
				if (arr != false) {
					key = this.toKey(arr);
					if (!aspects.has(key)) {
						aspects.set(key, nowKey);
						queue.push(next);

						if (key[2] == 'N') {
							while (key != "") {
								solution[0].unshift(key);
								key = aspects.get(key);
							}
							solution[1] = true;
							return solution;
						}
					}
				}
			}
		}
		return solution;
	}
	over(blocks) { //是否已经求解结束，得出正确结果
		let block;
		for (let i = 0; i < blocks.length; i++) {
			if (blocks[i].w == 2 && blocks[i].h == 2) {
				block = blocks[i];
				break;
			}
		}
		return block.x == 3 && block.y == 1;
	}
	correct(arr) { //局面是否正确
		let count = 0;
		for (let i = 0; i < 5; i++) {
			for (let j = 0; j < 4; j++) {
				if (arr[i][j] == 0) {
					count++;
				}
			}
		}
		return count == 2;
	}
	toArray(blocks) { //方块二维数组化
		let arr = [
			[0, 0, 0, 0],
			[0, 0, 0, 0],
			[0, 0, 0, 0],
			[0, 0, 0, 0],
			[0, 0, 0, 0]
		];
		for (let index = 0; index < blocks.length; index++) {
			let block = blocks[index];
			for (let i = block.x; i < block.x + block.h; i++) {
				for (let j = block.y; j < block.y + block.w; j++) {
					if (i >= 0 && j >= 0 && i < 5 && j < 4 && arr[i][j] == 0) {
						arr[i][j] = block.c;
					} else {
						return false;
					}
				}
			}
		}
		return arr;
	}
	toKey(arr) { //二维数组关键字化，方便排重，顺序：0X0->2X2->2X1->1X2
		let json = JSON.stringify(arr);
		arr = JSON.parse(json);
		let key = "";
		for (let i = 0; i < 5; i++) {
			for (let j = 0; j < 4; j++) {
				if (arr[i][j] == 0) {
					key += String.fromCharCode(i * 4 + j + 65);
					arr[i][j] = 5;
				}
			}
		}
		for (let i = 0; i < 5; i++) {
			for (let j = 0; j < 4; j++) {
				if (arr[i][j] == 1) {
					key += String.fromCharCode(i * 4 + j + 65);
					arr[i][j] = 5;
					arr[i + 1][j] = 5;
					arr[i + 1][j + 1] = 5;
					arr[i][j + 1] = 5;
				}
			}
		}
		for (let i = 0; i < 5; i++) {
			for (let j = 0; j < 4; j++) {
				if (arr[i][j] == 2) {
					key += String.fromCharCode(i * 4 + j + 65);
					arr[i][j] = 5;
					arr[i][j + 1] = 5;
				}
			}
		}
		for (let i = 0; i < 5; i++) {
			for (let j = 0; j < 4; j++) {
				if (arr[i][j] == 3) {
					key += String.fromCharCode(i * 4 + j + 65);
					arr[i][j] = 5;
					arr[i + 1][j] = 5;
				}
			}
		}
		return key;
	}
	cloneBlocks(blocks) { //复制方块数组
		let bs = [];
		for (let i = 0; i < blocks.length; i++) {
			bs.push(blocks[i].clone());
		}
		return bs;
	}
	keyToArray(key) { //key二维数组化

		let arr = [
			[4, 4, 4, 4],
			[4, 4, 4, 4],
			[4, 4, 4, 4],
			[4, 4, 4, 4],
			[4, 4, 4, 4]
		];
		let one = key.charCodeAt(0) - 65;
		let x = parseInt(one / 4);
		let y = one % 4;
		arr[x][y] = 0;
		let two = key.charCodeAt(1) - 65;
		x = parseInt(two / 4);
		y = two % 4;
		arr[x][y] = 0;
		let three = key.charCodeAt(2) - 65;
		x = parseInt(three / 4);
		y = three % 4;
		arr[x][y] = 1;
		arr[x + 1][y] = 1;
		arr[x + 1][y + 1] = 1;
		arr[x][y + 1] = 1;
		for (let i = 3; i < this.row + 3; i++) {
			let heng = key.charCodeAt(i) - 65;
			x = parseInt(heng / 4);
			y = heng % 4;
			arr[x][y] = 2;
			arr[x][y + 1] = 2;
		}
		for (let i = this.row + 3; i < key.length; i++) {
			let zong = key.charCodeAt(i) - 65;
			x = parseInt(zong / 4);
			y = zong % 4;
			arr[x][y] = 3;
			arr[x + 1][y] = 3;
		}
		return arr;
	}
	arrayToBlocks(arr) { //二维数组方块化
		let count = 0;
		let bs = [];
		while (count < 10) {
			for (let i = 0; i < 5; i++) {
				for (let j = 0; j < 4; j++) {
					if (arr[i][j] < 1) {
						continue;
					}
					if (arr[i][j] == 1) {
						bs.push(new Block(i, j, 2, 2));
						count++;
						arr[i][j] = -1;
						arr[i + 1][j] = -1;
						arr[i + 1][j + 1] = -1;
						arr[i][j + 1] = -1;
					} else if (arr[i][j] == 2) {
						count++;
						bs.push(new Block(i, j, 2, 1));
						arr[i][j] = -1;
						arr[i][j + 1] = -1;
					} else if (arr[i][j] == 3) {
						count++;
						bs.push(new Block(i, j, 1, 2));
						arr[i][j] = -1;
						arr[i + 1][j] = -1;
					} else {
						count++;
						bs.push(new Block(i, j, 1, 1));
						arr[i][j] = -1;
					}
				}
			}
		}
		return bs;
	}
}

// let blocks = [
// 	new Block(0, 0, 1, 2),
// 	new Block(0, 1, 2, 2),
// 	new Block(0, 3, 1, 2),
// 	new Block(2, 0, 1, 2),
// 	new Block(2, 1, 2, 1),
// 	new Block(2, 3, 1, 2),
// 	new Block(3, 1, 1, 1),
// 	new Block(3, 2, 1, 1),
// 	new Block(4, 0, 1, 1),
// 	new Block(4, 3, 1, 1)
// ];

let blocks = [
	new Block(0, 0, 1, 1),
	new Block(0, 1, 1, 1),
	new Block(0, 2, 1, 1),
	new Block(0, 3, 1, 2),
	new Block(1, 0, 2, 2),
	new Block(1, 2, 1, 2),
	new Block(2, 3, 1, 2),
	new Block(3, 0, 1, 1),
	new Block(3, 1, 2, 1),
	new Block(4, 2, 2, 1)
];

// let blocks = [
// 	new Block(0, 0, 1, 2),
// 	new Block(0, 1, 2, 2),
// 	new Block(0, 3, 1, 2),
// 	new Block(2, 0, 1, 2),
// 	new Block(2, 1, 1, 2),
// 	new Block(2, 2, 1, 1),
// 	new Block(2, 3, 1, 2),
// 	new Block(3, 2, 1, 1),
// 	new Block(4, 0, 1, 1),
// 	new Block(4, 3, 1, 1)
// ];

function draw(blocks) {
	let canvas = document.getElementsByTagName("canvas")[0];
	let context = canvas.getContext('2d');
	context.beginPath();
	context.fillStyle = "snow";
	context.fillRect(0, 0, 400, 500);
	context.closePath();

	let colors = ["Green", "Aqua", "CadetBlue", "Chocolate", "CornflowerBlue", "DarkKhaki", "DarkMagenta",
		"DarkGoldenrod", "DarkRed", "DimGray"
	];

	for (let i = 0; i < blocks.length; i++) {
		let x = blocks[i].y * 100;
		let y = blocks[i].x * 100;
		let width = blocks[i].w * 100;
		let height = blocks[i].h * 100;
		context.beginPath();
		// context.fillStyle = colors[i];
		
		if(blocks[i].w==2&&blocks[i].h==2){
			context.fillStyle=colors[1];
		}else if(blocks[i].w==2&&blocks[i].h==1){
			context.fillStyle=colors[0];
		}else if(blocks[i].w==1&&blocks[i].h==2){
			context.fillStyle=colors[2];
		}else{
			context.fillStyle=colors[3];
		}
		
		context.fillRect(x, y, width, height);
		context.strokeStyle="black";
		context.strokeRect(x,y,width,height);
		context.closePath();
	}
}

function go(blocks) {
	try {
		let s = new Solution(blocks);
		let result = s.solve();
		
		if(!result[1]){
			alert("无解");
		}else{
			for (let i = 0; i < result[0].length; i++) {
				let delay = (i + 1) * 1000;
				setTimeout(function() {
					let arr = s.keyToArray(result[0][i]);
					let bs = s.arrayToBlocks(arr);
					draw(bs);
				}, delay);
			}
		}
	} catch (e) {
		alert(e);
	}
}
